
@article{KerenS12,
  author    = {Keren Censor-Hillel and
               Hadas Shachnai},
  title     = {Fast Information Spreading in Graphs with Large Weak Conductance},
  journal   = {SIAM J. Comput.},
  volume    = {41},
  number    = {6},
  year      = {2012},
  pages     = {1451-1465},
}

@article{DasSarmaHKKNPPW12,
  author    = {Atish {Das Sarma} and
               Stephan Holzer and
               Liah Kor and
               Amos Korman and
               Danupon Nanongkai and
               Gopal Pandurangan and
               David Peleg and
               Roger Wattenhofer},
  title     = {Distributed Verification and Hardness of Distributed Approximation},
  journal   = {SIAM J. Comput.},
  volume    = {41},
  number    = {5},
  year      = {2012},
  pages     = {1235-1265}
}


@article{MatulaS90,
  author    = {David W. Matula and
               Farhad Shahrokhi},
  title     = {Sparsest cuts and bottlenecks in graphs},
  journal   = {Discrete Applied Mathematics},
  volume    = {27},
  number    = {1-2},
  year      = {1990},
  pages     = {113-123},
  }

@article{drw-jacm,
  author    = {Atish {Das Sarma} and
               Danupon Nanongkai and
               Gopal Pandurangan and
               Prasad Tetali},
  title     = {Distributed Random Walks},
  journal   = {J. ACM},
  volume    = {60},
  number    = {1},
  year      = {2013},
  pages     = {2},
}

@inproceedings{ManokaranNRS08,
  author    = {Rajsekar Manokaran and
               Joseph Naor and
               Prasad Raghavendra and
               Roy Schwartz},
  title     = {Sdp gaps and ugc hardness for multiway cut, 0-extension,
               and metric labeling},
  booktitle = {STOC},
  year      = {2008},
  pages     = {11-20},
}

@article{Karger00,
  author    = {David R. Karger},
  title     = {Minimum cuts in near-linear time},
  journal   = {J. ACM},
  volume    = {47},
  number    = {1},
  year      = {2000},
  pages     = {46-76},
}

@inproceedings{BenczurK96,
  author    = {Andr{\'a}s A. Bencz{\'u}r and
               David R. Karger},
  title     = {Approximating {\it s-t} Minimum Cuts in {\it {\~O}}({\it n}$^{\mbox{2}}$)
               Time},
  booktitle = {STOC},
  year      = {1996},
  pages     = {47-55},
}

@article{BhattL84,
  author    = {Sandeep N. Bhatt and
               Frank Thomson Leighton},
  title     = {A Framework for Solving VLSI Graph Layout Problems},
  journal   = {J. Comput. Syst. Sci.},
  volume    = {28},
  number    = {2},
  year      = {1984},
  pages     = {300-343},
 }

@article{mcm-avrachenkov,
author = "K. Avrachenkov and N. Litvak and D. Nemirovsky and N. Osipova",
title = "Monte Carlo methods in PageRank computation: When one iteration is sufficient",
journal = {SIAM J. Number. Anal.},
volume = {45(2)},
year = {2007},
pages = {890--904}
}

@article{ppr-bahmani2010,
 author = {B. Bahmani and A. Chowdhury and A. Goel},
 title = {Fast incremental and personalized PageRank},
 journal ={PVLDB},
 volume = {4},
 year = {2010},
 pages = {173-184}
 }

@inproceedings{anatomy+page98,
       booktitle = {Seventh International World-Wide Web Conference (WWW 1998)},
           title = {The Anatomy of a Large-Scale Hypertextual Web Search Engine},
          author = {S. Brin and L. Page},
            year = {1998},
            pages ={107-117},
             url = {http://ilpubs.stanford.edu:8090/361/}
             }

@article{page99,
author ={L. Page and S. Brin and R. Motwani and T. Winograd}, 
title ={The PageRank citation ranking: Bringing order to the web}, 
journal ={Technical report, Stanford InfoLab}, 
year ={1999},
} 

@inproceedings{DasSarmaMPU13,
  author    = {Atish {Das Sarma} and
               Anisur Rahaman Molla and
               Gopal Pandurangan and
               Eli Upfal},
  title     = {Fast Distributed PageRank Computation},
  booktitle = {ICDCN},
  year      = {2013},
  pages     = {11-26},
 }

@inproceedings{OrecchiaSVV08,
  author    = {Lorenzo Orecchia and
               Leonard J. Schulman and
               Umesh V. Vazirani and
               Nisheeth K. Vishnoi},
  title     = {On partitioning graphs via single commodity flows},
  booktitle = {STOC},
  year      = {2008},
  pages     = {461-470},
}

@inproceedings{KhandekarRV06,
  author    = {Rohit Khandekar and
               Satish Rao and
               Umesh V. Vazirani},
  title     = {Graph partitioning using single commodity flows},
  booktitle = {STOC},
  year      = {2006},
  pages     = {385-390},
}

@inproceedings{AroraK07,
  author    = {Sanjeev Arora and
               Satyen Kale},
  title     = {A combinatorial, primal-dual approach to semidefinite programs},
  booktitle = {STOC},
  year      = {2007},
  pages     = {227-236},
}

@inproceedings{AroraHK04,
  author    = {Sanjeev Arora and
               Elad Hazan and
               Satyen Kale},
  title     = {O(sqrt (log n)) Approximation to SPARSEST CUT in {\~O}(n$^{\mbox{2}}$)
               Time},
  booktitle = {FOCS},
  year      = {2004},
  pages     = {238-247},
}

@inproceedings{SimaS06,
  author    = {Jir\'{\i} S\'{\i}ma and
               Satu Elisa Schaeffer},
  title     = {On the NP-Completeness of Some Graph Cluster Measures},
  booktitle = {SOFSEM},
  year      = {2006},
  pages     = {530-537},
}

@article{LeightonR99,
  author    = {Frank Thomson Leighton and
               Satish Rao},
  title     = {Multicommodity max-flow min-cut theorems and their use in
               designing approximation algorithms},
  journal   = {J. ACM},
  volume    = {46},
  number    = {6},
  year      = {1999},
  pages     = {787-832},
  }

@article{KannanVV04,
  author    = {Ravi Kannan and
               Santosh Vempala and
               Adrian Vetta},
  title     = {On clusterings: Good, bad and spectral},
  journal   = {J. ACM},
  volume    = {51},
  number    = {3},
  year      = {2004},
  pages     = {497-515},
}

@inproceedings{DasSarmaGP09,
  author    = {Atish {Das Sarma} and
               Sreenivas Gollapudi and
               Rina Panigrahy},
  title     = {Sparse Cut Projections in Graph Streams},
  booktitle = {ESA},
  year      = {2009},
  pages     = {480-491},
}

@inproceedings{JerrumS88,
  author    = {Mark Jerrum and
               Alistair Sinclair},
  title     = {Conductance and the Rapid Mixing Property for Markov Chains:
               the Approximation of the Permanent Resolved},
  booktitle = {STOC},
  year      = {1988},
  pages     = {235-244},
}

@inproceedings{Boppana87,
  author    = {Ravi B. Boppana},
  title     = {Eigenvalues and Graph Bisection: An Average-Case Analysis},
  booktitle = {FOCS},
  year      = {1987},
  pages     = {280-285},
  }

@article{Alon86,
  author    = {Noga Alon},
  title     = {Eigenvalues and expanders},
  journal   = {Combinatorica},
  volume    = {6},
  number    = {2},
  year      = {1986},
  pages     = {83-96},
}

@inproceedings{AroraRV04,
  author    = {Sanjeev Arora and
               Satish Rao and
               Umesh V. Vazirani},
  title     = {Expander flows, geometric embeddings and graph partitioning},
  booktitle = {STOC},
  year      = {2004},
  pages     = {222-231},
}

@inproceedings{AndersenCL06,
  author    = {Reid Andersen and
               Fan R. K. Chung and
               Kevin J. Lang},
  title     = {Local Graph Partitioning using PageRank Vectors},
  booktitle = {FOCS},
  year      = {2006},
  pages     = {475-486},
}

@inproceedings{SpielmanT04,
  author    = {Daniel A. Spielman and
               {Shang-Hua} Teng},
  title     = {Nearly-linear time algorithms for graph partitioning, graph
               sparsification, and solving linear systems},
  booktitle = {STOC},
  year      = {2004},
  pages     = {81-90},
}

@article{LovaszS93,
  author    = {L{\'a}szl{\'o} Lov{\'a}sz and
               Mikl{\'o}s Simonovits},
  title     = {Random Walks in a Convex Body and an Improved Volume Algorithm},
  journal   = {Random Struct. Algorithms},
  volume    = {4},
  number    = {4},
  year      = {1993},
  pages     = {359-412},
}

@inproceedings{LovaszS90,
  author    = {L{\'a}szl{\'o} Lov{\'a}sz and
               Mikl{\'o}s Simonovits},
  title     = {The Mixing Rate of Markov Chains, an Isoperimetric Inequality,
               and Computing the Volume},
  booktitle = {FOCS},
  year      = {1990},
  pages     = {346-354},
}

@article{disc-arxiv,
  author    = {Atish {Das Sarma} and
               Anisur Rahaman Molla and
               Gopal Pandurangan},
  title     = {Fast Distributed Computation in Dynamic Networks via Random
               Walks},
  journal   = {CoRR},
  volume    = {abs/1205.5525},
  year      = {2012},
  ee        = {http://arxiv.org/abs/1205.5525},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{disc12,
  author    = {Atish {Das Sarma} and
               Anisur Rahaman Molla and
               Gopal Pandurangan},
  title     = {Fast Distributed Computation in Dynamic Networks via Random Walks},
  booktitle = {Proc. of 26th International Symposium on Distributed Computing (DISC)},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {7611},
  year      = {2012},
  pages     = {136-150},
}

@inproceedings{FOCS2001,
 author = {Gopal Pandurangan and Prabhakar Raghavan and Eli Upfal},
 title = {Building Low-Diameter Peer-to-Peer Networks},
 booktitle ={Proc. of 42nd IEEE Symposium on Foundations of Computer Science (FOCS)},
 year = {2001},
 pages     = {492-499},
 }

@inproceedings{clementi-podc12,
 author = {Andrea Clementi and Riccardo Silvestri and Luca Trevisan},
 title = {Information Spreading in Dynamic Graphs},
 booktitle = {Proc. of 31th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
 year = {2012},
 Pages ={37-46}
 }


@inproceedings{dynamic-survey,
 author = {Casteigts, Arnaud and Flocchini, Paola and Quattrociocchi, Walter and Santoro, Nicola},
 title = {Time-varying graphs and dynamic networks},
 booktitle = {Proc. of 10th International Conference on Ad Hoc Networks and Wireless (ADHOC-NOW)},
 year = {2011},
 pages = {346--359},
 acmid = {2032496},
}

@inproceedings{JGPE:soda12,
 author = {Augustine, J. and Pandurangan, G. and Robinson, P and Upfal, E},
 title = {Towards Robust and Efficient Computation in Dynamic Peer-to-Peer Networks},
 booktitle = {Proc. of ACM-SIAM Symposium on Discrete Algorithm (SODA)},
 year = {2012},
 pages     = {551-569},
 }

@article{Bat,
 author = {Benjamini, I. and Kozma, G. and Lov\'{a}sz, L. and Romik, D. and Tardos, G.},
 title = {Waiting for a bat to fly by (in polynomial time)},
 journal = {IEEE/ACM Trans. Netw.},
 volume = {15},
 issue = {5},
 month = {September},
 year = {2006},
} 


@article{deb+mc:coding,
 author = {Deb, S. and M\'{e}dard, M. and Choute, C.},
 title = {Algebraic gossip: a network coding approach to optimal multiple rumor mongering},
 journal = {Combinatorics, Probability and Computing},
 volume = {14},
 month = {June},
 year = {2006},
 pages = {2486--2507},
} 

@inproceedings{shah,
 author = {Damon Mosk-Aoyama and Devavrat Shah},
 title = {Computing separable functions via gossip},
 booktitle = {PODC},
 year = {2006},
 pages = {113--122}
 }

@inproceedings{avin1, 
author = {Chen Avin and Michael Borokhovich and Keren Censor-Hillel and Zvi Lotker},
title = {Order Optimal Information Spreading Using Algebraic Gossip},
booktitle = {Proc. of 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
year = {2011},
pages = {363-372}
}


@inproceedings{avin2,
author = {Michael Borokhovich and Chen Avin and Zvi Lotker},
title = {Tight Bounds for Algebraic Gossip on Graphs},
booktitle = {IEEE ISIT},
year = {2010}
}

@inproceedings{haeupler:gossip,
 author = {Haeupler, Bernhard},
 title = {Analyzing network coding gossip made easy},
 booktitle = {Proc. of 43nd Symposium on Theory of Computing (STOC)},
 year = {2011},
 pages = {293--302},
} 

@inproceedings{haeupler+k:dynamic,
 author = {Haeupler, Bernhard and Karger, David},
 title = {Faster information dissemination in dynamic networks via network coding},
 booktitle = {Proc. of 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
 year = {2011},
 pages = {381--390},
} 

@INPROCEEDINGS{berenbrink+ceg:gossip,
AUTHOR = "Petra Berenbrink and Jurek Czyzowicz and Robert Els{\"{a}}sser and Leszek Gasieniec",
TITLE = "Efficient Information Exchange in the Random Phone-Call Model",
booktitle = {Proc. of 37th Coll. on Automata, Languages and Programming (ICALP)},
PAGES = {127-138},
YEAR = {2010}  }

@inproceedings{kuhn-podc, 
 author = {Fabian Kuhn and Rotem Oshman and Yoram Moses},
 title = {Coordinated consensus in dynamic networks}, 
 booktitle = {Proc. of 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
 pages = {1-10},
 year ={ 2011 }
  }  

@inproceedings{kuhn+lo:dynamic,
 author = {Kuhn, Fabian and Lynch, Nancy and Oshman, Rotem},
 title = {Distributed computation in dynamic networks},
 booktitle = {ACM STOC},
 year = {2010},
 pages = {513--522},
} 

@inproceedings{CMMPS08,
  author    = {A. Clementi and
               C. Macci and 
               A. Monti and
               F. Pasquale and
               R. Silvestri},
  title     = {Flooding time in edge-Markovian dynamic graphs},
  booktitle = {Proc. of 27th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
  year      = {2008},
  pages     = {213-222}
}

@inproceedings{BCF09,
  author    = {H. Baumann and
               P. Crescenzi and 
               P. Fraigniaud},
  title     = {Parsimonious flooding in dynamic graphs},
  booktitle = {Proc. of 28th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
  year      = {2009},
  pages     = {260-269}
}

@inproceedings{DPRS-arxiv,
  author    = {Chinmoy Dutta and
               Gopal Pandurangan and Rajmohan Rajaraman and Zhifeng Sun and Emanuele Viola},
  title     = {On the Complexity of Information Spreading in Dynamic Networks},
 booktitle = {Proc. of ACM-SIAM Symposium on Discrete Algorithm (SODA)},
 year      = {2013},
}

@book{Levin,
 author = {David A. Levin and Yuval Peres and Elizabeth L. Wilmer},
 title = {Markov Chains and Mixing times},
 year = {2008},
 publisher = {American Mathematical Society},
 address = {Providence, RI, USA}
 }

@inproceedings{DasSarmaNPT10,
  author    = {Atish {Das Sarma} and
               Danupon Nanongkai and
               Gopal Pandurangan and
               Prasad Tetali},
  title     = {Efficient distributed random walks with applications},
  booktitle = {PODC},
  year      = {2010},
  pages     = {201-210}
}

@inproceedings{NanongkaiDP11,
  author    = {Danupon Nanongkai and
               Atish {Das Sarma} and
               Gopal Pandurangan},
  title     = {A tight unconditional lower bound on distributed randomwalk
               computation},
  booktitle = {Proc. of  30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
  year      = {2011},
  pages     = {257-266}
}

@inProceedings{Kuhn-stoc,
author = {F. Kuhn and N. Lynch and R. Oshman},
title = {Distributed computation in dynamic networks},
booktitle = {Proc. of 42nd Symposium on Theory of Computing (STOC)},
pages = {513--522},
year = {2010}
}

@article{GH09,
author = "P. Grindrod and D. J. Higham",
title = "Evolving graphs: dynamical models, inverse problems and propagation",
journal = {Proc. of the Royal Society A: Mathematical, Physical and Engineering Sciences},
volume = {466(2115)},
year = {2009},
pages = {753--770}
}

@article{FGM09,
author = "A. Ferreia and A. Goldman and J. Monteiro",
title = "Performance evaluation of routing protocols for MANETs with known connectivity patterns using evolving graphs",
journal = {Wireless Networks},
volume = {16(3)},
year = {2009},
pages = {627--640}
}

@article{Feria04,
author = "A. Ferreia",
title = "Building a reference combinatorial model for MANETs",
journal = {IEEE Network Magazine},
volume = {18(5)},
year = {2004},
pages = {24--29}
}

@inProceedings{AKL08,
author = {C. Avin and M. Kouck{\'y} and Z. Lotker},
title = {How to explore a fast-changing world (cover time of a simple random walk on evolving graphs)},
booktitle = {Proc. of 35th Coll. on Automata, Languages and Programming (ICALP)},
pages = {121--132},
year = {2008}
}

@InProceedings{mihail-topaware,
  author = 	 {C. Gkantsidis and G. Goel and M. Mihail and A. Saberi},
  title = 	 {Towards Topology Aware Networks},
  booktitle = 	 {IEEE INFOCOM},
  year = 	 {2007}
}

@article{elkin-survey,
    author = "M. Elkin",
    title = "An Overview of Distributed Approximation",
    journal = {ACM SIGACT News Distributed Computing Column},
    year = {2004},
    month = {December},
    volume = {35},
    number = {4},
    pages = {40--57}    
}

@incollection{dubhashi,
author = "D. Dubhashi and F. Grandioni and A. Panconesi",
title  = "Distributed Algorithms via LP Duality and Randomization",
booktitle  =  "Handbook of Approximation Algorithms and Metaheuristics",
year =  2007
}

@article{khan-disc,
 author = {M. Khan and G. Pandurangan},
 title = {A Fast Distributed Approximation Algorithm for Minimum Spanning Trees},
 journal = {Distributed Computing},
 year = {2008},
 volume = {20},
 pages = {391-402}
}

@InProceedings{khan-podc,
author = {M. Khan and  F. Kuhn and D. Malkhi and G. Pandurangan and K. Talwar},
title = {Efficient Distributed Approximation Algorithms via Probabilistic Tree
Embeddings},
booktitle = {Proc. 27th ACM Symposium on Principles of Distributed Computing (PODC)},
year = {2008}
}

@article{kutten-domset,
    author = "S. Kutten and D. Peleg",
    title = "Fast distributed construction of k-dominating sets and applications",
    journal = {J. Algorithms},
    year = {1998},
    volume = {28},
    pages = {40--66}
}

@article{kempe,
author = {D. Kempe and F. McSherry},
title=  {A Decentralized Algorithm for Spectral Analysis},
 journal = {Journal of 
Computer and System Sciences}, 
volume = {74(1)},
year = {2008},
pages = {70-83}
}


@InProceedings{BFFKRW,
  author = 	 {T. Batu and E. Fischer and L. Fortnow and R. Kumar and R. Rubenfeld and P. White},
  title = 	 {Testing Random Variables for Independence and Identity},
  booktitle = 	 {Proc. of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS)},
  pages = 	 {442--451},
  year = 	 {2001}
}

@Article{JS89,
  author = 	 {M. Jerrum and A. Sinclair},
  title = 	 {Approximating the permanent},
  journal = 	 {SIAM Journal of Computing},
  year = 	 {1989},
  volume = 	 {18},
  number = 	 {6},
  pages = 	 {1149--1178}
}

@misc{LPW,
  title={{Markov chains and mixing times}},
  author={Levin, D.A. and Y.(Yuval) Peres and Elizabeth L.(Elizabeth Lee) Wilmer},
  year={2009},
  publisher={American Mathematical Society}
}

@article{Lyons,
  author    = {Russell Lyons},
  title     = {Asymptotic Enumeration of Spanning Trees},
  journal   = {Combinatorics, Probability {\&} Computing},
  volume    = {14},
  number    = {4},
  year      = {2005},
  pages     = {491-522},
  ee        = {http://dx.doi.org/10.1017/S096354830500684X},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{Vitter85,
  author    = {Jeffrey Scott Vitter},
  title     = {Random Sampling with a Reservoir},
  journal   = {ACM Trans. Math. Softw.},
  volume    = {11},
  number    = {1},
  year      = {1985},
  pages     = {37-57},
  note      = {Also appeared in FOCS'83},
  ee        = {http://doi.acm.org/10.1145/3147.3165},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@INPROCEEDINGS(mihail,
 author =     {C. Gkantsidis and  M. Mihail and A. Saberi},
 title =       {Throughput and Congestion in Power-Law Graphs},
booktitle = {SIGMETRICS},
 pages =       {148-159},
  year =     {2003}
  )

@article(dinwoodie,
author = {I. H. Dinwoodie},
title = {A Probability Inequality for the Occupation Measure of a Reversible Markov Chain},
journal = {The Annals of Applied Probability},
volume = {5(1)},
year =  {1995},
pages = {37-43}
)

@INPROCEEDINGS(elkin,
 author = {Elkin, M.},
 title = {Unconditional Lower Bounds on the Time-Approximation Tradeoffs for the Distributed Minimum Spanning Tree Problem},
 booktitle = {Proceedings of Symposium on Theory of Computing (STOC)},
 year = {2004},
 month = {June},
 CITY = "Chicago",
 COUNTRY = "USA",
)

@inproceedings{DNP09-podc,
  author    = {Atish {Das Sarma} and
               Danupon Nanongkai
               and Gopal Pandurangan},
  title     = {Fast Distributed Random Walks},
  booktitle = {Proc. of 28th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)},
  year      = {2009},
  pages     = {161-170},
}

@BOOK(lynch,
 author = {N. Lynch},
 title = {Distributed Algorithms},
 publisher = {Morgan Kaufmann Publishers, San Mateo, CA},
 year = {1996}
)

@BOOK(tel,
 author = {Gerard Tel},
 title = {Introduction to Distributed Algorithms},
 publisher = {Cambridge University Press, UK},
 year = {1994}
)

@inproceedings{peleg-bound,
    author = "D. Peleg and V. Rabinovich",
    title = "A near-tight lower bound on the time complexity of distributed MST construction",
    booktitle = "Proc. of the 40th IEEE Symp. on Foundations of Computer Science",
    pages = "253--261",
    year = "1999"
}


@article{frieze,
  author    = {Colin Cooper and
               Alan M. Frieze and
               Tomasz Radzik},
  title     = {Multiple Random Walks in Random Regular Graphs},
  journal   = {SIAM J. Discrete Math.},
  volume    = {23},
  number    = {4},
  year      = {2009},
  pages     = {1738-1761},
}


@article{Gillman98,
  author    = {David Gillman},
  title     = {A Chernoff Bound for Random Walks on Expander Graphs},
  journal   = {SIAM J. Comput.},
  volume    = {27},
  number    = {4},
  year      = {1998},
  pages     = {1203-1220},
  ee        = {http://epubs.siam.org/sam-bin/dbq/article/26876},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}


@article{Jonasson98,
  author    = {Johan Jonasson},
  title     = {On the Cover Time for Random Walks on Random Graphs},
  journal   = {Combinatorics, Probability {\&} Computing},
  volume    = {7},
  number    = {3},
  year      = {1998},
  pages     = {265-279}
}

@inproceedings{Wilson96,
  author    = {David Bruce Wilson},
  title     = {Generating Random Spanning Trees More Quickly than the Cover
               Time},
  booktitle = {STOC},
  year      = {1996},
  pages     = {296-303},
  ee        = {http://doi.acm.org/10.1145/237814.237880}
}


@ARTICLE{JS00,
    author = {Johan Jonasson and Oded Schramm},
    title = {On the cover time of planar graphs},
    journal = {Elec. Comm. Probab},
    year = {2000},
    volume = {5},
    pages = {85-90}
}

@inproceedings{CooperF03,
  author    = {Colin Cooper and
               Alan M. Frieze},
  title     = {The cover time of sparse random graphs},
  booktitle = {SODA},
  year      = {2003},
  pages     = {140-147},
  ee        = {http://doi.acm.org/10.1145/644108.644134}
}


@inproceedings{BroderK88,
  author    = {Andrei Z. Broder and
               Anna R. Karlin},
  title     = {Bounds on the Cover Time (Preliminary Version)},
  booktitle = {FOCS},
  year      = {1988},
  pages     = {479-487}
}


@inproceedings{ChandraRRST89,
  author    = {Ashok K. Chandra and
               Prabhakar Raghavan and
               Walter L. Ruzzo and
               Roman Smolensky and
               Prasoon Tiwari},
  title     = {The Electrical Resistance of a Graph Captures its Commute
               and Cover Times (Detailed Abstract)},
  booktitle = {STOC},
  year      = {1989},
  pages     = {574-586}
}


@article{ST08,
  author    = {Rahul Sami and
               Andy Twigg},
  title     = {Lower bounds for distributed markov chain problems},
  journal   = {CoRR},
  volume    = {abs/0810.5263},
  year      = {2008},
  ee        = {http://arxiv.org/abs/0810.5263}
}

@article{AHLP01,
  author    = {Lada A. Adamic and
               Rajan M. Lukose and
               Amit R. Puniyani and
               Bernardo A. Huberman},
  title     = {Search in Power-Law Networks},
  journal   = {Physical Review},
  volume    = {64},
  year      = {2001},
  ee        = {http://arxiv.org/abs/cs.NI/0103016}
}

@inproceedings{BAS04,
  author    = {Ashwin R. Bharambe and
               Mukesh Agrawal and
               Srinivasan Seshan},
  title     = {Mercury: supporting scalable multi-attribute range queries},
  booktitle = {SIGCOMM},
  year      = {2004},
  pages     = {353-366},
  ee        = {http://doi.acm.org/10.1145/1015467.1015507}
}

@inproceedings{LCCLS02,
  author    = {Qin Lv and
               Pei Cao and
               Edith Cohen and
               Kai Li and
               Scott Shenker},
  title     = {Search and replication in unstructured peer-to-peer networks},
  booktitle = {ICS},
  year      = {2002},
  pages     = {84-95},
  ee        = {http://doi.acm.org/10.1145/514191.514206}
}

@inproceedings{GMS05,
  author    = {Christos Gkantsidis and
               Milena Mihail and
               Amin Saberi},
  title     = {Hybrid search schemes for unstructured peer-to-peer networks},
  booktitle = {INFOCOM},
  year      = {2005},
  pages     = {1526-1537},
  ee        = {http://dx.doi.org/10.1109/INFCOM.2005.1498436}
}

@inproceedings{C05,
  author    = {Brian F. Cooper},
  title     = {Quickly Routing Searches Without Having to Move Content},
  booktitle = {IPTPS},
  year      = {2005},
  pages     = {163-172},
  ee        = {http://dx.doi.org/10.1007/11558989_15}
}


@article{ZS06,
  author    = {Ming Zhong and
               Kai Shen},
  title     = {Random walk based node sampling in self-organizing networks},
  journal   = {Operating Systems Review},
  volume    = {40},
  number    = {3},
  year      = {2006},
  pages     = {49-55},
  ee        = {http://doi.acm.org/10.1145/1151374.1151386}
}

@inproceedings{KKD01,
  author    = {David Kempe and
               Jon M. Kleinberg and
               Alan J. Demers},
  title     = {Spatial gossip and resource location protocols},
  booktitle = {STOC},
  year      = {2001},
  pages     = {163-172},
  ee        = {http://doi.acm.org/10.1145/380752.380796}
}

@inproceedings{K00,
  author    = {Jon M. Kleinberg},
  title     = {The small-world phenomenon: an algorithm perspective},
  booktitle = {STOC},
  year      = {2000},
  pages     = {163-170},
  ee        = {http://doi.acm.org/10.1145/335305.335325}
}

@inproceedings{KR04,
  author    = {David R. Karger and
               Matthias Ruhl},
  title     = {Simple efficient load balancing algorithms for peer-to-peer
               systems},
  booktitle = {SPAA},
  year      = {2004},
  pages     = {36-43},
  ee        = {http://doi.acm.org/10.1145/1007912.1007919}
}

@inproceedings{ZSS05,
  author    = {Ming Zhong and
               Kai Shen and
               Joel I. Seiferas},
  title     = {Non-uniform random membership management in peer-to-peer
               networks},
  booktitle = {INFOCOM},
  year      = {2005},
  pages     = {1151-1161},
  ee        = {http://dx.doi.org/10.1109/INFCOM.2005.1498342}
}

@article{MRRT53,
    abstract = {A general method, suitable for fast computing machines, for investigating such properties as equations of state for substances consisting of interacting individual molecules is described. The method consists of a modified Monte Carlo integration over configuration space. Results for the two-dimensional rigid-sphere system have been obtained on the Los Alamos MANIAC and are presented here. These results are compared to the free volume equation of state and to a four-term virial coefficient expansion.
    The Journal of Chemical Physics is copyrighted by The American Institute of Physics.},
    author = {Metropolis, Nicholas   and Rosenbluth, Arianna  W.  and Rosenbluth, Marshall  N.  and Teller, Augusta  H.  and Teller, Edward  },
    citeulike-article-id = {531300},
    doi = {http://dx.doi.org/10.1063/1.1699114},
    journal = {The Journal of Chemical Physics},
    keywords = {annealing, simulated},
    number = {6},
    pages = {1087--1092},
    posted-at = {2007-07-12 12:49:56},
    priority = {2},
    publisher = {AIP},
    title = {Equation of State Calculations by Fast Computing Machines},
    url = {http://dx.doi.org/10.1063/1.1699114},
    volume = {21},
    year = {1953}
}

@article{Hastings70,
    abstract = {A generalization of the sampling method introduced by Metropolis et al. (1953) is presented along with an exposition of the relevant theory, techniques of application and methods and difficulties of assessing the error in Monte Carlo estimates. Examples of the methods, including the generation of random orthogonal matrices and potential applications of the methods to numerical problems arising in statistics, are discussed. 10.1093/biomet/57.1.97},
    author = {Hastings, W. K. },
    citeulike-article-id = {1015842},
    doi = {http://dx.doi.org/10.1093/biomet/57.1.97},
    journal = {Biometrika},
    keywords = {approximate-methods, bayesian},
    month = {April},
    number = {1},
    pages = {97--109},
    posted-at = {2008-10-31 16:19:43},
    priority = {2},
    title = {Monte Carlo sampling methods using Markov chains and their applications},
    url = {http://dx.doi.org/10.1093/biomet/57.1.97},
    volume = {57},
    year = {1970}
}

@inproceedings{LawS03,
  author    = {Ching Law and
               Kai-Yeung Siu},
  title     = {Distributed Construction of Random Expander Networks},
  booktitle = {INFOCOM},
  year      = {2003},
  ee        = {http://www.ieee-infocom.org/2003/papers/52_02.PDF}
}

@book{chung,
 author = {Fan Chung},
 title = {Spectral Graph Theory},
 year = {1997},
 publisher = {American Mathematical Society},
 address = {Providence, RI, USA}
 }


@book{peleg,
 author = {David Peleg},
 title = {Distributed computing: a locality-sensitive approach},
 year = {2000},
 isbn = {0-89871-464-8},
 publisher = {SIAM},
 address = {Philadelphia, PA, USA},
 }


@inproceedings{PK09,
  author    = {Gopal Pandurangan and Maleq Khan},
  title     = {Theory of Communication Networks},
  booktitle = {Algorithms and Theory of Computation Handbook, Second Edition},
  year      = {2009},
  PUBLISHER =    {CRC Press},
}




@inproceedings{AKL+79,
  author    = {Romas Aleliunas and
               Richard M. Karp and
               Richard J. Lipton and
               L{\'a}szl{\'o} Lov{\'a}sz and
               Charles Rackoff},
  title     = {Random Walks, Universal Traversal Sequences, and the Complexity
               of Maze Problems},
  booktitle = {FOCS},
  year      = {1979},
  pages     = {218-223}
}



@article{BFG+03,
 author = {H. Baala and O. Flauzac and J. Gaber and M. Bui and T. El-Ghazawi},
 title = {A self-stabilizing distributed algorithm for spanning tree construction in wireless ad hoc networks},
 journal = {J. Parallel Distrib. Comput.},
 volume = {63},
 number = {1},
 year = {2003},
 issn = {0743-7315},
 pages = {97--104},
 doi = {http://dx.doi.org/10.1016/S0743-7315(02)00028-X},
 publisher = {Academic Press, Inc.},
 address = {Orlando, FL, USA},
 }

@inproceedings{GoyalRV09,
  author    = {Navin Goyal and
               Luis Rademacher and
               Santosh Vempala},
  title     = {Expanders via random spanning trees},
  booktitle = {SODA},
  year      = {2009},
  pages     = {576-585},
  ee        = {http://doi.acm.org/10.1145/1496770.1496834}
}

@inproceedings{LKRG03,
  author    = {Dmitri Loguinov and
               Anuj Kumar and
               Vivek Rai and
               Sai Ganesh},
  title     = {Graph-theoretic analysis of structured peer-to-peer systems:
               routing distances and fault resilience},
  booktitle = {SIGCOMM},
  year      = {2003},
  pages     = {395-406},
  ee        = {http://doi.acm.org/10.1145/863955.863999}
}


@article{AlonAKKLT11,
  author    = {Noga Alon and
               Chen Avin and
               Michal Kouck{\'y} and
               Gady Kozma and
               Zvi Lotker and
               Mark R. Tuttle},
  title     = {Many Random Walks Are Faster Than One},
  journal   = {Combinatorics, Probability {\&} Computing},
  volume    = {20},
  number    = {4},
  year      = {2011},
  pages     = {481-502},
}


@INPROCEEDINGS(costsens,
author = {B. Awerbuch and A. Baratz and D. Peleg},
 title = {Cost-sensitive analysis of communication protocols},
booktitle =  {  9th ACM PODC},
 pages = {177-187},
 year ={ 1990}
 )

@article{AP92,
 author = {Baruch Awerbuch and David Peleg},
 title = {Routing with polynomial communication-space trade-off},
 journal = {SIAM J. Discret. Math.},
 volume = {5},
 number = {2},
 year = {1992},
 issn = {0895-4801},
 pages = {151--162},
 doi = {http://dx.doi.org/10.1137/0405013},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
 }

@article{AtishGP11,
  author    = {Atish {Das Sarma} and
               Sreenivas Gollapudi and
               Rina Panigrahy},
  title     = {Estimating PageRank on graph streams},
  journal   = {J. ACM},
  volume    = {58},
  number    = {3},
  year      = {2011},
  pages     = {13},
  }

@book{MU-book-05,
 author = {Michael Mitzenmacher and Eli Upfal},
 title = {Probability and Computing: Randomized Algorithms and Probabilistic Analysis},
 year = {2005},
 isbn = {0521835402},
 publisher = {Cambridge University Press},
 address = {New York, NY, USA},
 }

@inproceedings{IJ90,
  author    = {Amos Israeli and
               Marc Jalfon},
  title     = {Token Management Schemes and Random Walks Yield Self-Stabilizing
               Mutual Exclusion},
  booktitle = {PODC},
  year      = {1990},
  pages     = {119-131},
  ee        = {http://doi.acm.org/10.1145/93385.93409}
}


@inproceedings{BBF04,
  author    = {Thibault Bernard and
               Alain Bui and
               Olivier Flauzac},
  title     = {Random Distributed Self-stabilizing Structures Maintenance},
  booktitle = {ISSADS},
  year      = {2004},
  pages     = {231-240},
  ee        = {http://springerlink.metapress.com/openurl.asp?genre=article{\&}issn=0302-9743{\&}volume=3061{\&}spage=231}
}

@article{CTW93,
 author = {Don Coppersmith and Prasad Tetali and Peter Winkler},
 title = {Collisions among random walks on a graph},
 journal = {SIAM J. Discret. Math.},
 volume = {6},
 number = {3},
 year = {1993},
 issn = {0895-4801},
 pages = {363--374},
 doi = {http://dx.doi.org/10.1137/0406029},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
 }

@article{DSW06,
  author    = {Shlomi Dolev and
               Elad Schiller and
               Jennifer L. Welch},
  title     = {Random Walk for Self-Stabilizing Group Communication in
               Ad Hoc Networks},
  journal   = {IEEE Trans. Mob. Comput.},
  volume    = {5},
  number    = {7},
  year      = {2006},
  pages     = {893-905},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/TMC.2006.104},
  note      = {also in PODC'02}
}


@inproceedings{DSW02,
  author    = {Shlomi Dolev and
               Elad Schiller and
               Jennifer L. Welch},
  title     = {Random walk for self-stabilitzing group communication in
               ad hoc networks},
  booktitle = {PODC},
  year      = {2002},
  pages     = {259},
  ee        = {http://doi.acm.org/10.1145/571825.571872}
}


@article{DT07,
  title={{Spanders: Distributed spanning expanders}},
  author={Dolev, S. and Tzachar, N.},
  journal={Dept. of Computer Science, Ben-Gurion University, TR-08-02},
  year={2007}
}


@inproceedings{Broder89,
  author    = {Andrei Z. Broder},
  title     = {Generating Random Spanning Trees},
  booktitle = {FOCS},
  year      = {1989},
  pages     = {442-447}
}


@inproceedings{BIZ89,
 author = {Judit Bar-Ilan and Dror Zernik},
 title = {Random Leaders and Random Spanning Trees},
 booktitle = {Proceedings of the 3rd International Workshop on Distributed Algorithms},
 year = {1989},
 isbn = {3-540-51687-5},
 pages = {1--12},
 publisher = {Springer-Verlag},
 address = {London, UK},
 }

@inproceedings{BBSB04,
  author    = {Marc Bui and
               Thibault Bernard and
               Devan Sohier and
               Alain Bui},
  title     = {Random Walks in Distributed Computing: A Survey},
  booktitle = {Proc. of 4th International Workshop on Innovative Internet Community Systems (IICS)},
  year      = {2004},
  pages     = {1-14},
  ee        = {http://dx.doi.org/10.1007/11553762_1}
}

@inproceedings{MG07,
  author    = {Rams{\'e}s Morales and
               Indranil Gupta},
  title     = {AVMON: Optimal and Scalable Discovery of Consistent Availability
               Monitoring Overlays for Distributed Systems},
  booktitle = {ICDCS},
  year      = {2007},
  pages     = {55},
  ee        = {http://doi.ieeecomputersociety.org/10.1109/ICDCS.2007.87}
  }


 @article{GKM03,
 author = {Ayalvadi J. Ganesh and Anne-Marie Kermarrec and Laurent Massouli\'{e}},
 title = {Peer-to-Peer Membership Management for Gossip-Based Protocols},
 journal = {IEEE Trans. Comput.},
 volume = {52},
 number = {2},
 year = {2003},
 issn = {0018-9340},
 pages = {139--149},
 doi = {http://dx.doi.org/10.1109/TC.2003.1176982},
 publisher = {IEEE Computer Society},
 address = {Washington, DC, USA},
 }
